2017年信息学奥赛NOIP普及组
初赛
更早
2023-08-24 13:14:32
43次
一、单选题
二、填空题
#include <iostream>
using namespace std;
int main() {
string ch;
int a[200];
int b[200];
int n, i, t, res;
cin >> ch;
n = ch.length();
for (i = 0; i < 200; i++)
b[i] = 0;
for (i = 1; i <= n; i++) {
a[i] = ch[i - 1] - '0';
b[i] = b[i - 1] + a[i];
}
res = b[n];
t = 0;
for (i = n; i > 0; i--) {
if (a[i] == 0)
t++;
if (b[i - 1] + t < res)
res = b[i - 1] + t;
}
cout << res << endl;
return 0;
}输入： 1001101011001101101011110001
输出：
【知识点】 信息学NOIP普及组
#include <iostream>
using namespace std;
int g(int m, int n, int x) {
int ans = 0;
int i;
if (n == 1)
return 1;
for (i = x; i <= m / n; i++)
ans += g(m - i, n - 1, i);
return ans;
}
int main() {
int t, m, n;
cin >> m >> n;
cout << g(m, n, 0) << endl;
return 0;
}输入： 7 3
输出：
【知识点】 信息学NOIP普及组
#include <iostream>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
int x = 1;
int y = 1;
int dx = 1;
int dy = 1;
int cnt = 0;
while (cnt != 2) {
cnt = 0;
x = x + dx;
y = y + dy;
if (x == 1 || x == n) {
++cnt;
dx = -dx;
}
if (y == 1 || y == m) {
++cnt;
dy = -dy;
}
}
cout << x << " " << y << endl;
return 0;
}输入 1：4 3
输出 1： （3 分）
输入 2：2017 1014
输出 2： （5 分）
【知识点】 信息学NOIP普及组
#include <iostream>
using namespace std;
int main() {
int t[256];
string s;
int i;
cin >> s;
for (i = 0; i < 256; i++)
t[i] = 0;
for (i = 0; i < s.length(); i++)
t[s[i]]++;
for (i = 0; i < s.length(); i++)
if (t[s[i]] == 1) {
cout << s[i] << endl;
return 0;
}
cout << "no" << endl;
return 0;
}输入： xyzxyw
输出：
【知识点】 信息学NOIP普及组
三、简答题
（切割绳子）有n条绳子，每条绳子的长度已知且均为正整数。绳子可以以任意正整数长度切割，但不可以连接。现在要从这些绳子中切割出m条长度相同的绳段，求绳段的最大长度是多少。（第一、二空2.5分，其余3分）
输入：第一行是一个不超过100的正整数n，第二行是n个不超过106的正整数，表示每条绳子的长度，第三行是一个不超过108的正整数m。
输出：绳段的最大长度，若无法切割，输出Failed。
#include <iostream>
using namespace std;
int n, m, i, lbound, ubound, mid, count;
int len[100]; // 绳子长度
int main() {
cin >> n;
count = 0;
for (i = 0; i < n; i++) {
cin >> len[i];
(1) ;
}
cin >> m;
if ( (2) ) {
cout << "Failed" << endl;
return 0;
}
lbound = 1;
ubound = 1000000;
while ( (3) ) {
mid = (4) ;
count = 0;
for (i = 0; i < n; i++)
(5) ;
if (count < m)
ubound = mid - 1;
else
lbound = mid;
}
cout << lbound << endl;
return 0;
}
【知识点】 信息学NOIP普及组
（快速幂）请完善下面的程序，该程序使用分治法求xp mod m的值。（第一空 2 分，其余 3 分）
输入：三个不超过10000的正整数x，p，m。
输出：xp mod m的值。
提示：若p为偶数，xp=(x2)p/2；若p为奇数，xp=x*(x2)(p-1)/2。
#include <iostream>
using namespace std;
int x, p, m, i, result;
int main() {
cin >> x >> p >> m;
result = (1) ;
while ( (2) ) {
if (p % 2 == 1)
result = (3) ;
p /= 2;
x = (4) ;
}
cout << (5) << endl;
return 0;
}
【知识点】 信息学NOIP普及组
